{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Words Within Two Edits of Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: twoEditWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #距离字典两次编辑以内的单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串数组&nbsp;<code>queries</code> 和&nbsp;<code>dictionary</code>&nbsp;。数组中所有单词都只包含小写英文字母，且长度都相同。</p>\n",
    "\n",
    "<p>一次 <strong>编辑</strong>&nbsp;中，你可以从 <code>queries</code>&nbsp;中选择一个单词，将任意一个字母修改成任何其他字母。从&nbsp;<code>queries</code>&nbsp;中找到所有满足以下条件的字符串：<strong>不超过</strong>&nbsp;两次编辑内，字符串与&nbsp;<code>dictionary</code>&nbsp;中某个字符串相同。</p>\n",
    "\n",
    "<p>请你返回<em>&nbsp;</em><code>queries</code>&nbsp;中的单词列表，这些单词距离&nbsp;<code>dictionary</code>&nbsp;中的单词&nbsp;<strong>编辑次数</strong>&nbsp;不超过&nbsp;<strong>两次</strong>&nbsp;。单词返回的顺序需要与&nbsp;<code>queries</code>&nbsp;中原本顺序相同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>queries = [\"word\",\"note\",\"ants\",\"wood\"], dictionary = [\"wood\",\"joke\",\"moat\"]\n",
    "<b>输出：</b>[\"word\",\"note\",\"wood\"]\n",
    "<strong>解释：</strong>\n",
    "- 将 \"word\" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 \"wood\" 。\n",
    "- 将 \"note\" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 \"joke\" 。\n",
    "- \"ants\" 需要超过 2 次编辑才能得到 dictionary 中的单词。\n",
    "- \"wood\" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。\n",
    "所以我们返回 [\"word\",\"note\",\"wood\"] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>queries = [\"yes\"], dictionary = [\"not\"]\n",
    "<b>输出：</b>[]\n",
    "<strong>解释：</strong>\n",
    "\"yes\" 需要超过 2 次编辑才能得到 \"not\" 。\n",
    "所以我们返回空数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= queries.length, dictionary.length &lt;= 100</code></li>\n",
    "\t<li><code>n == queries[i].length == dictionary[j].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li>所有&nbsp;<code>queries[i]</code> 和&nbsp;<code>dictionary[j]</code>&nbsp;都只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [words-within-two-edits-of-dictionary](https://leetcode.cn/problems/words-within-two-edits-of-dictionary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [words-within-two-edits-of-dictionary](https://leetcode.cn/problems/words-within-two-edits-of-dictionary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"word\",\"note\",\"ants\",\"wood\"]\\n[\"wood\",\"joke\",\"moat\"]', '[\"yes\"]\\n[\"not\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if sum(c1 != c2 for c1, c2 in zip(q, d)) < 3:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "\n",
    "        def canMatch(word1, word2):\n",
    "            count = 0\n",
    "            for c1, c2 in zip(word1, word2):\n",
    "                if c1 != c2:\n",
    "                    count += 1\n",
    "                    if count > 2:\n",
    "                        return False\n",
    "            return count <= 2\n",
    "\n",
    "        result = []\n",
    "        for query in queries:\n",
    "            for word in dictionary:\n",
    "                if canMatch(query, word):\n",
    "                    result.append(query)\n",
    "                    break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                c = 0\n",
    "                for a, b in zip(q, d):\n",
    "                    if a != b:\n",
    "                        c += 1\n",
    "                        if c > 2:\n",
    "                            break\n",
    "                else:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for cnt in queries:\n",
    "            n = len(cnt)\n",
    "            if cnt in dictionary:\n",
    "                ans.append(cnt)\n",
    "            else:\n",
    "                for temp in dictionary:\n",
    "                    if sum(x!=y for x,y in zip(cnt,temp))<=2:\n",
    "                        ans.append(cnt)\n",
    "                        break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def numdiff(word1, word2):\n",
    "            ans = 0\n",
    "            for i in range(len(word1)):\n",
    "                if word1[i] != word2[i]: ans += 1\n",
    "                if ans > 2: return ans\n",
    "            return ans\n",
    "        anslis = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if numdiff(q, d) <= 2: \n",
    "                    anslis.append(q)\n",
    "                    break\n",
    "        return anslis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ret=[]\n",
    "        for i,q in enumerate(queries):\n",
    "            \n",
    "            for j,d in enumerate(dictionary):\n",
    "                n,m=len(q),len(d)\n",
    "                if n!=m:\n",
    "                    continue\n",
    "                limit=2\n",
    "                flag=True\n",
    "                for k in range(n):\n",
    "                    if q[k]!=d[k]:\n",
    "                        if not limit:\n",
    "                            flag=False\n",
    "                            break\n",
    "                        else:\n",
    "                            limit-=1\n",
    "                if flag:\n",
    "                    ret.append(q)\n",
    "                    break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            for t in dictionary:\n",
    "                d = 0\n",
    "                for c1, c2 in zip(s, t):\n",
    "                    d += c1 != c2\n",
    "                if d <= 2:\n",
    "                    res.append(s)\n",
    "                    break\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        result = list()\n",
    "\n",
    "        for que in queries:\n",
    "            for dic in dictionary:\n",
    "                if sum([x != y for x, y in zip(que, dic)]) <= 2:\n",
    "                    result.append(que)\n",
    "                    break\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for cnt in queries:\n",
    "            n = len(cnt)\n",
    "            if cnt in dictionary:\n",
    "                ans.append(cnt)\n",
    "            else:\n",
    "                for temp in dictionary:\n",
    "                    if sum(x!=y for x,y in zip(cnt,temp))<=2:\n",
    "                        ans.append(cnt)\n",
    "                        break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def g(x,y):\n",
    "            c=0\n",
    "            for i,j in zip(x,y):\n",
    "               if i!=j:\n",
    "                c+=1\n",
    "            return c \n",
    "        ans=[]\n",
    "        for x in queries:\n",
    "            for j in dictionary:\n",
    "                if g(x,j)<=2:\n",
    "                    ans.append(x)\n",
    "                    break\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if sum(x!=y for x,y in zip(q,d))<=2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        n = len(dictionary)\n",
    "        l = len(queries[0])\n",
    "        for q in queries:\n",
    "            p = [0]*n\n",
    "            for i in range(l):\n",
    "                for j in range(n):\n",
    "                    if p[j] < 3 and q[i] != dictionary[j][i]:\n",
    "                        p[j] += 1\n",
    "            if sum(c < 3 for c in p) > 0:\n",
    "                res.append(q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isMatch(query, word):\n",
    "            if len(query) != len(word):\n",
    "                return False\n",
    "            count = 0\n",
    "            for i in range(len(query)):\n",
    "                if query[i] != word[i]:\n",
    "                    count += 1\n",
    "                    if count > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        result = []\n",
    "        for query in queries:\n",
    "            for word in dictionary:\n",
    "                if isMatch(query, word):\n",
    "                    result.append(query)\n",
    "                    break\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        wordn = len(queries[0])\n",
    "        ans = []\n",
    "        for s1 in queries:\n",
    "            for s2 in dictionary:\n",
    "                temp = 0\n",
    "                for i in range(wordn):\n",
    "                    if s1[i] != s2[i]:\n",
    "                        temp += 1\n",
    "                    if temp > 2:\n",
    "                        break\n",
    "                if temp <= 2:\n",
    "                    ans.append(s1)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def twoWordsless(word1, word2):\n",
    "            n = len(word2)\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                if word1[i] != word2[i]:\n",
    "                    count += 1\n",
    "                if count > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        out = []\n",
    "        length_q = len(queries)\n",
    "        length_d = len(dictionary)\n",
    "        for j in range(length_q):\n",
    "            for k in range(length_d):\n",
    "                if twoWordsless(queries[j], dictionary[k]):\n",
    "                    out.append(queries[j])\n",
    "                    break\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if len(q) != len(s):\n",
    "                    continue\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if sum(s != t for s, t in zip(q, d)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if sum( x!=y for x,y in zip(q,d))<=2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        for sq in queries:\n",
    "            for sd in dictionary:\n",
    "                t=0\n",
    "                for i in range(len(sq)):\n",
    "                    if sq[i]!=sd[i]:\n",
    "                        t+=1\n",
    "                if t<=2:\n",
    "                    res.append(sq)\n",
    "                    break\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def diff(q, w):\n",
    "            return sum(a != b for a, b in zip(q, w))\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if diff(q, d) <= 2:\n",
    "                    res.append(q)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if sum(a != b for a, b in zip(q, d)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans=[]\n",
    "        n=len(queries[0])\n",
    "        for i in queries:\n",
    "            for j in dictionary:\n",
    "                cnt=0\n",
    "                for k in range(n):\n",
    "                    cnt+=not i[k]==j[k]\n",
    "                if cnt<=2:\n",
    "                    ans.append(i)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            for t in dictionary:\n",
    "                if sum(x!=y for x,y in zip(s,t))<=2:\n",
    "                    res.append(s)\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        n = len(queries[0])\n",
    "        ret = []\n",
    "        for q in queries:\n",
    "            for x in dictionary:\n",
    "                cnt = sum(q[i] != x[i] for i in range(n))\n",
    "                if cnt <= 2:\n",
    "                    ret.append(q)\n",
    "                    break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        if not queries:\n",
    "            return []\n",
    "        ret = []\n",
    "        l = len(queries[0])\n",
    "        if l <= 2:\n",
    "            return queries\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                cnt = 0\n",
    "                is_ret = True\n",
    "                for i in range(l):\n",
    "                    if q[i] != d[i]:\n",
    "                        cnt += 1\n",
    "                        if cnt > 2:\n",
    "                            is_ret = False\n",
    "                            break\n",
    "                if is_ret:\n",
    "                    ret.append(q)\n",
    "                    break\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res=[]\n",
    "        for w1 in queries:\n",
    "            for w2 in dictionary:\n",
    "                trans = 0\n",
    "                for i,j in zip(w1,w2):\n",
    "                    if i!= j:\n",
    "                        trans +=1\n",
    "                if trans <= 2:\n",
    "                    res.append(w1)\n",
    "                    break\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries, dictionary) :\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            \n",
    "            for d in dictionary:\n",
    "                times = 0\n",
    "                for c1,c2 in zip(q,d):\n",
    "                    if c1!=c2:\n",
    "                        times+=1\n",
    "                if times<=2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        #两次编辑:  相异字母小于等于两个\n",
    "        def fun(a,b):\n",
    "            dif = 0\n",
    "            for aa, bb in zip(a,b): #计算不同字母数\n",
    "                if aa != bb:\n",
    "                    dif += 1\n",
    "            return dif < 3\n",
    "        \n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            for y in dictionary:\n",
    "                if fun(x,y):\n",
    "                    ans+= x,\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def match(s1: str, s2: str) -> bool:\n",
    "            count = 0\n",
    "            for i, c in enumerate(s1):\n",
    "                if c != s2[i]:\n",
    "                    count += 1\n",
    "                    if count > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        res = []\n",
    "        for target in queries:\n",
    "            for word in dictionary:\n",
    "                if match(target, word):\n",
    "                    res.append(target)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                count, flag = 0, False\n",
    "                for c1, c2 in zip(q, d):\n",
    "                    if c1 != c2:\n",
    "                        count += 1\n",
    "                        if count > 2:\n",
    "                            flag = True\n",
    "                            break\n",
    "                if not flag:\n",
    "                    res.append(q)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def isSimilar(qWord, dWord):\n",
    "            if len(qWord) != len(dWord):\n",
    "                return False\n",
    "            difcount = 0\n",
    "            for i in range(len(qWord)):\n",
    "                if qWord[i] != dWord[i]:\n",
    "                    difcount += 1\n",
    "                if difcount > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            for d in dictionary:\n",
    "                if isSimilar(query, d):\n",
    "                    res.append(query)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for tmp1 in queries:\n",
    "            for tmp2 in dictionary:\n",
    "                if len(tmp1) != len(tmp2):\n",
    "                    continue\n",
    "                p = 0\n",
    "                count = 0\n",
    "                while p < len(tmp1):\n",
    "                    if tmp1[p] != tmp2[p]:\n",
    "                        count += 1\n",
    "                    p += 1\n",
    "                if count <= 2:\n",
    "                    res.append(tmp1)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        n = len(queries[0])\n",
    "        for i in queries:\n",
    "            for j in dictionary:\n",
    "                if sum([1 for k in range(n) if j[k]==i[k]]) >= n-2:\n",
    "                    res.append(i)\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def diff(w1,w2):\n",
    "            n = len(w1)\n",
    "            check = 0\n",
    "            for i in range(n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    check += 1\n",
    "                if check > 2:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for d in dictionary:\n",
    "                if diff(q,d):\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        \n",
    "        def check(s, t):\n",
    "            n = len(s)\n",
    "            return sum(s[i]!=t[i] for i in range(n))\n",
    "        ans = []\n",
    "        for word in queries:\n",
    "            if any(check(word, st)<=2 for st in dictionary):\n",
    "                ans.append(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x!=y for x, y in zip(q,s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def is_two(q,d):\n",
    "            flag = 0\n",
    "            for d1 in d:\n",
    "                n = len(d1)\n",
    "                num = 0\n",
    "                for i in range(n):\n",
    "                    if q[i] == d1[i]:\n",
    "                        num += 1\n",
    "                if n-num<=2:\n",
    "                    flag = 1\n",
    "                    break\n",
    "            return flag\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            if is_two(q,dictionary):\n",
    "                res.append(q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans,n = [],len(queries[0])\n",
    "        for i in queries:\n",
    "            f = False\n",
    "            for j in dictionary:\n",
    "                tmp = 0\n",
    "                for k in range(n):\n",
    "                    if i[k] != j[k]:\n",
    "                        tmp += 1\n",
    "                    if tmp > 2:\n",
    "                        break\n",
    "                if tmp <= 2:\n",
    "                    f = True\n",
    "                    break\n",
    "            if f:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        def edit_distance(s1, s2):\n",
    "            count = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i] != s2[i]:\n",
    "                    count += 1\n",
    "                    if count > 2:  # 如果编辑次数超过2，直接返回\n",
    "                        return count\n",
    "            return count\n",
    "\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            found = False\n",
    "            for word in dictionary:\n",
    "                if edit_distance(query, word) <= 2:\n",
    "                    res.append(query)\n",
    "                    found = True\n",
    "                    break\n",
    "            if not found:\n",
    "                res.append(\"\")  # 如果没有找到，添加空字符串，这样可以保持原来的顺序\n",
    "        return [word for word in res if word]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            for s in dictionary:\n",
    "                if sum(x != y for x, y in zip(q, s)) <= 2:\n",
    "                    ans.append(q)\n",
    "                    break\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
